/*
 * BinomialTree.java
 *
 * Created on July 26, 2004, 6:30 PM
 */

package com.milowski.monos.binomial;

import java.util.*;
import com.milowski.monos.monomial.*;

/**
 *
 * @author  R. Alexander Milowski
 */
public class BinomialTree extends MonomialTree {
   
   class CompactBinomialDivisorIterator extends TreeIterator {

      boolean first;
      short [] values;
      
     CompactBinomialDivisorIterator(short [] v,boolean first,int width,Entry root) {
         super(false,width, root);
         this.first = first;
         this.values = v;
      }
      
      short value() {
         return first ? (values[level]>0 ? values[level] : 0) : 
                        (values[level]<0 ? (short)-values[level] : 0);
      }
      
      protected void seek() {
         // If we're finished, there is nothing to do.
         if (finished) {
            return;
         }
         // If the current position hasn't been consumed, there is nothing to do.
         if (!consumed) {
            return;
         }
         
         //log.info("(started,consumed,finished)=("+started+","+consumed+","+finished+")");
         // If we've started, we need to find the next left-most matching tree
         if (started) {
            do {
               // back to first entry with right sibling that is less than the value
               while (level>=0 && (current[level].rightSibling==null || current[level].rightSibling.value>value())) {
                  level--;
               }
               // If level is negative, we're done.
               if (level<0) {
                  finished = true;
                  return;
               }

               // Otherwise, seek to next minimal position

               // move to right sibling
               current[level] = current[level].rightSibling;

               // move to left-most subtree
               for (int i=level+1; i<current.length; i++) {
                  level++;
                  current[level] = current[level-1].firstChild;
                  if (current[level]==null || current[level].value>value()) {
                     level--;
                     break;
                  }
               }
            } while (level!=(current.length-1));
            consumed = false;

         } else {
            
            // otherwise, we need to initialize to the first divisor
            
            started = true;
            level = 0;
            current[level] = top.firstChild;
            // check no first entry or no divisors
            if (current[level]==null || current[level].value>value()) {
               finished = true;
               return;
            }
            
            // initialize to the left subtree
            for (int i=1; i<current.length; i++) {
               level++;
               current[level] = current[level-1].firstChild;
               if (current[level].value>value()) {
                  level--;
                  break;
               }
            }
            
            if (level!=(current.length-1)) {
               // The left-most subtree doesn't divide, so seek to the next position
               seek();
            } else {
               consumed = false;
            }
         }
         
      }
      
   }
   
   public static class BinomialDivisorIterator extends TreeIterator {

      short [] values;
      
      BinomialDivisorIterator(short [] v,int width,Entry root) {
         super(false,width,root);
         this.values = v;
      }
      
      public void setDivided(short [] v) {
         this.values = v;
         started = false;
         finished = false;
         consumed = true;
         top = root;
         // The above is the same as reset()
         //reset();
      }
      
      protected void seek() {
         while (true) {
            // If we're finished, there is nothing to do.
            if (finished) {
               return;
            }
            // If the current position hasn't been consumed, there is nothing to do.
            if (!consumed) {
               return;
            }

            //log.info("(started,consumed,finished)=("+started+","+consumed+","+finished+")");
            // If we've started, we need to find the next left-most matching tree
            if (started) {
               do {
                  // back to first entry with right sibling that is less than the value
                  while (level>=0 && (current[level].rightSibling==null || current[level].rightSibling.value>values[level])) {
                     level--;
                  }
                  // If level is negative, we're done.
                  if (level<0) {
                     finished = true;
                     return;
                  }

                  // Otherwise, seek to next minimal position

                  // move to right sibling
                  current[level] = current[level].rightSibling;

                  // move to left-most subtree
                  for (int i=level+1; i<current.length; i++) {
                     level++;
                     current[level] = current[level-1].firstChild;
                     if (current[level]==null || current[level].value>values[level]) {
                        level--;
                        break;
                     }
                  }
               } while (level!=(current.length-1));
               consumed = false;

            } else {

               // otherwise, we need to initialize to the first divisor

               started = true;
               level = 0;
               current[level] = top.firstChild;
               // check no first entry or no divisors
               if (current[level]==null || current[level].value>values[level]) {
                  finished = true;
                  return;
               }

               // initialize to the left subtree
               for (int i=1; i<current.length; i++) {
                  level++;
                  current[level] = current[level-1].firstChild;
                  if (current[level].value>values[level]) {
                     level--;
                     break;
                  }
               }

               if (level!=(current.length-1)) {
                  // The left-most subtree doesn't divide, so seek to the next position
                  //seek();
               } else {
                  consumed = false;
               }
            }
         }
      }
      public Object next() {
         if (!started || consumed) {
            seek();
         }
         if (!finished) {
            consumed = true;

            return ((EntryWithData)current[level]).data;
         } else {
            return null;
         }
      }
            
   }
   
   /** Creates a new instance of BinomialTree */
   public BinomialTree(LexOrder order) {
      super(order);
   }
   
   public boolean containsBinomial(Binomial b,boolean first) {
      return containsBinomial(first ? b.getLeadingTerm() : b.getTrailingTerm(),first);
   }
   
   public boolean containsBinomial(short [] values,boolean first) {
      boolean contained = true;
      Entry current = root.getFirstChild();
      int level = 0;
      do {
         short value = first ? (values[level]>0 ? values[level] : 0) :
                               (values[level]<0 ? (short)-values[level] : 0);
         while (current!=null && current.getValue()<value) {
            current = current.getRightSibling();
         }
         if (current==null) {
            contained = false;
         } else if (current.getValue()==value) {
            level++;
            current = current.getFirstChild();
         } else {
            contained = false;
         }
      } while (contained && level<values.length);
      
      return contained;
   }

   public boolean removeBinomial(Binomial b,boolean first) {
      return removeBinomial(first ? b.getLeadingTerm() : b.getTrailingTerm(),b,first);
   }
   
   public boolean removeBinomial(short [] values,Object leafTarget,boolean first) {
      boolean contained = true;
      Entry current = root.firstChild;
      int level = 0;
      do {
         short value = first ? (values[level]>0 ? values[level] : 0) :
                               (values[level]<0 ? (short)-values[level] : 0);
         while (current!=null && current.value<value) {
            current = current.rightSibling;
         }
         if (current==null) {
            contained = false;
         } else if (current.value==value) {
            workTemp[level] = current;
            level++;
            current = current.firstChild;
         } else {
            contained = false;
         }
      } while (contained && level<values.length);
      
      if (contained) {
         EntryWithData leaf = (EntryWithData)workTemp[workTemp.length-1];
         //Object o = leafMap.get(leaf);
         Object o = leaf.data;
         if (o instanceof List) {
            List l = (List)o;
            l.remove(leafTarget);
            if (l.size()==1) {
               //leafMap.put(leaf,l.get(0));
               leaf.setData(l.get(0));
            }
         } else {
            //leafMap.remove(leaf);
            level = workTemp.length-1;
            if (workTemp[level-1].leafCount==1) {
               // Only child
               
               // Find the first level where there is not one leaf
               // TODO: the extra check isn't needed but the leaf count has gotten messed up.
               Entry lastOneLeaf = null;
               while (level>=0 && (workTemp[level].leafCount==1 || workTemp[level].firstChild.rightSibling==null)) {
                  lastOneLeaf = workTemp[level];
                  level--;
               }
               
               // We may have gone all the way to the root
               Entry currentRoot = level<0 ? root : workTemp[level];

               // Find the the last entry with one leaf
               current = currentRoot.firstChild;
               Entry last = null;
               while (current!=lastOneLeaf) {
                  last = current;
                  current = current.rightSibling;
               }
               
               // Remove that entry
               if (last==null && current.rightSibling==null) {
                  throw new RuntimeException("Whooah!");
               } else {
                  if (last==null) {
                     currentRoot.setFirstChild(current.rightSibling);
                  } else {
                     last.setRightSibling(current.rightSibling);
                  }
                  currentRoot.setLeafCount(currentRoot.leafCount-1);
               }
               
               // Return the subtree to the pool
               pool.put(lastOneLeaf);
            } else {
               
               // We have more than one leaf, so just remove the found leaf

               // Find the current leaf
               current = workTemp[level-1].firstChild;
               Entry last = null;
               while (current!=leaf) {
                  last = current;
                  current = current.rightSibling;
               }
               
               // Remove the leaf
               if (last==null) {
                  workTemp[level-1].firstChild = current.rightSibling;
               } else {
                  last.rightSibling = current.rightSibling;
               }
               current.leafCount--;
               
               // Return the leaf to the pool
               pool.put(workTemp[level]);
            }
         }
      }
      
      return contained;
   }

   public Iterator compactBinomialDivisors(short [] b,boolean first) {
      return new CompactBinomialDivisorIterator(b,first,width,root);
   }
   
   public BinomialDivisorIterator binomialDivisors(short [] b) {
      return new BinomialDivisorIterator(b,width,root);
   }
   
   public Iterator binomialDivisors(CompactBinomial b,boolean first) {
      return new CompactBinomialDivisorIterator(b.getValues(),first,width,root);
   }

   public BinomialDivisorIterator binomialDivisors(Binomial b,boolean first) {
      return new BinomialDivisorIterator(first ? b.getLeadingTerm() : b.getTrailingTerm(),width,root);
   }

   public boolean dividesBinomial(Binomial b,boolean first) {
      return firstDivisorOfBinomial(first ? b.getLeadingTerm() : b.getTrailingTerm(),first)!=null;
   }
   public boolean dividesBinomial(short [] values,boolean first) {
      return firstDivisorOfBinomial(values,first)!=null;
   }
   
   public Entry [] firstDivisorOfBinomial(short [] values,boolean first) {
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      
      int level = 0;
      boolean divided = false;
      Entry current = root.getFirstChild();
      while (!divided && current!=null) {
         short value = first ? (values[level]>0 ? values[level] : 0) :
                               (values[level]<0 ? (short)-values[level] : 0);
         if (current.getValue()<=value) {
            workTemp[level] = current;
            level++;
            current = current.getFirstChild();
            if (current==null) {
               divided = true;
            }
         } else {
            current = current.getRightSibling();
            while (current==null && level!=0) {
               level--;
               current = workTemp[level].getRightSibling();
            }
         }
      }

      return divided ? workTemp : null;
   
   }
   
   public void addBinomials(List binomials) {
      addBinomials(binomials,true);
   }
   
   public void addBinomials(List binomials,boolean first) {
      Iterator toAdd = binomials.iterator();
      while (toAdd.hasNext()) {
         Binomial b = (Binomial)toAdd.next();
         addBinomial(b,first);
      }
   }
   
   public boolean addBinomial(Binomial b) {
      return addBinomial(b,true);
   }
   
   public boolean addBinomial(CompactBinomial b,boolean first) {
      return addBinomial(b.getValues(),b,first);
   }
      
   public boolean addBinomial(Binomial b,boolean first) {
      return addBinomial(first ? b.getLeadingTerm() : b.getTrailingTerm(),b,first);
   }
      
   public boolean addBinomial(short [] values,Object leafTarget,boolean first) {
      if (width<=0) {
         width = values.length;
      }
      int sum = 0;
      for (int i=0; i<values.length; i++) {
         sum += values[i];
      }
      if (sum==0) {
         throw new IllegalArgumentException("Zero binomials are not allowed in the tree.");
      }
      
      if (workTemp==null) {
         workTemp = new Entry[width];
      }
      
      boolean added = false;
      Entry current = root;
      
      for (int i=0; i<width; i++) {
         // Add to the tree

         boolean isLeaf = (i+1)==width;

         // Search for existing entry at this level
         Entry child = current.firstChild;
         Entry found = null;
         workTemp[i] = current;
         short value = first ? (values[i]>0 ? values[i] : 0) : (values[i]<0 ? (short)-values[i] : 0); 
         while (found==null && child!=null) {
            if (finestLog) {
               log.finest(i+": Checking children item "+child.value+" for "+value);
            }
            if (child.value==value) {
               found = child;
            }
            child = child.rightSibling;
         }

         if (found==null) {
            // Create a new entry
            current = current.addChild(isLeaf ? new EntryWithData(null, leafTarget) : pool.get(),value);
            if (finestLog) {
               log.finest(i+": adding "+value+", v="+current+", v.right="+current.rightSibling);
            }
            nodeCount++;
            if (isLeaf) {
               /*
               if (leafMap==null) {
                  leafMap = new HashMap();
               }
               leafMap.put(current,leafTarget);
                */
               //((EntryWithData)current).setData(leafTarget);
            }
            if (!added) {
               added = true;
               for (int t=0; t<=i; t++) {
                  workTemp[t].leafCount++;
               }
            }
         } else {
            // Otherwise, just traverse level
            if (finestLog) {
               log.finest(i+": found "+value);
            }
            current = found;
            if (isLeaf) {
               /*
               if (leafMap==null) {
                  leafMap = new HashMap();
               }
               Object currData = leafMap.get(current);
                */
               Object currData = ((EntryWithData)current).data;
               if (currData instanceof List) {
                  ((List)currData).add(leafTarget);
               } else {
                  List l = new ArrayList();
                  l.add(currData);
                  l.add(leafTarget);
                  //leafMap.put(current,l);
                  ((EntryWithData)current).data = l;
               }
            }
         }
      }
      return added;
   }
   
   public void groebnerReduce(boolean first) {
      boolean opposite = !first;
      minimize();
      //Iterator binomials = leafMap==null ? Collections.EMPTY_LIST.iterator() :  leafMap.values().iterator();
      Iterator binomials = iterator();
      List toRemove = new ArrayList();
      while (binomials.hasNext()) {
         Object o = binomials.next();
         Binomial best;
         if (o instanceof List) {
            //log.info("processing conflict, size="+((List)o).size());
            Iterator belements = ((List)o).iterator();
            best = (Binomial)belements.next();
            int index=0;
            short [] bvalues = best.getTrailingTerm();
            for (; index<bvalues.length && bvalues[index]!=0; index++);
            while (belements.hasNext()) {
               Binomial b = (Binomial)belements.next();
               if (b instanceof CompactBinomial) {
                  bvalues = ((CompactBinomial)b).getValues();
                  int firstExp = 0;
                  for (; firstExp<bvalues.length && bvalues[firstExp]>=0; firstExp++);
                  if (firstExp<index) {
                     index = firstExp;
                     toRemove.add(best);
                     best = b;
                  } else {
                     toRemove.add(b);
                  }
               } else {
                  bvalues = b.getTrailingTerm();
                  int firstExp = 0;
                  for (; firstExp<bvalues.length && bvalues[firstExp]==0; firstExp++);
                  if (firstExp<index) {
                     index = firstExp;
                     toRemove.add(best);
                     best = b;
                  } else {
                     toRemove.add(b);
                  }
               }
            }
         } else {
            best = (Binomial)o;
         }
         // Check to see if leading term is in LT(basis)
         Iterator binomialDivisors = binomialDivisors(best,true);
         boolean other = false;
         while (!other && binomialDivisors.hasNext()) {
            if (binomialDivisors.next()!=best) {
               toRemove.add(best);
               other = true;
            }
         }
         if (!other) {
            // Check to see if trailing term is in LT(basis)
            binomialDivisors = binomialDivisors(best,false);
            while (!other && binomialDivisors.hasNext()) {
               if (binomialDivisors.next()!=best) {
                  toRemove.add(best);
                  other = true;
               }
            }
         }
      }
      binomials = toRemove.iterator();
      while (binomials.hasNext()) {
         Binomial b = (Binomial)binomials.next();
         //log.info("Removing "+arrayToString(b.getValues()));
         removeBinomial(b,first);
      }
   }
   
   private String arrayToString(short [] values) {
      StringBuffer sb = new StringBuffer();
      for (int i=0; i<values.length; i++) {
         if (i!=0) {
            sb.append(' ');
         }
         sb.append(values[i]);
      }
      return sb.toString();
   }
   
}
